#include <iostream>
#include <vector>
#include <algorithm> // 用于min
using namespace std;

// 计算数塔的最小路径和
int minimumTotal(const vector<vector<int>>& triangle) {
    int n = triangle.size();
    // 创建备忘录
    vector<vector<int>> dp(n, vector<int>(n, 0));
    // 自下而上进行填表
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= i; j++) { // 注意这里的范围是0到i
            if (i == n - 1)
                dp[i][j] = triangle[i][j];
            else
                dp[i][j] = triangle[i][j] + 
                    min(dp[i + 1][j], dp[i + 1][j + 1]);
        }
    }
    // 完成填表并返回结果
    return dp[0][0];
}

int main() {
    // 定义数塔
    vector<vector<int>> triangle = {
        {9},
        {13, 16},
        {4, 10, 7},
        {9, 11, 6, 13},
        {17, 5, 19, 11, 10}
    };

    int ans = minimumTotal(triangle);
    cout << "最小路径和为: " << ans << endl;

    return 0;
}